1651C - Fault-tolerant Network - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define foru(i, a, b) for (int i = a; i <= b; ++i)
#define ford(i, a, b) for (int i = a; i >= b; --i)
#define endl '\n'
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define bit(x, k) (((x) >> (k)) & 1ll)
#define on(x, k) ((x) | (1ll << (k)))
#define off(x, k) ((x) & (~(1ll << (k))))
#define ms(x, y) memset(x, y, sizeof(x))
const ll mod = 1e9 + 7;
const ll base = 31;
const ll maxn = 2e5 + 5;
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
    }
    int dau1 = a.front(), cuoi1 = a.back();
    // a.pop_back();
    // reverse(all(a));
    // a.pop_back();
    // reverse(all(a));
    int dau2 = b.front(), cuoi2 = b.back();
    // b.pop_back();
    // reverse(all(b));
    // b.pop_back();
    // reverse(all(b));
    sort(all(a));
    sort(all(b));
    map<ll, ll> opt;
    auto it = lower_bound(all(b), dau1);
    if (it == b.end())
        --it;
    if (it == b.begin())
        opt[dau1] = abs(*it - dau1);
    else
        opt[dau1] = min(abs(*it - dau1), abs(*(it - 1) - dau1));

    it = lower_bound(all(b), cuoi1);
    if (it == b.end())
        --it;
    if (it == b.begin())
        opt[cuoi1] = abs(*it - cuoi1);
    else
        opt[cuoi1] = min(abs(*it - cuoi1), abs(*(it - 1) - cuoi1));

    it = lower_bound(all(a), dau2);
    if (it == a.end())
        --it;
    if (it == a.begin())
        opt[dau2] = abs(*it - dau2);
    else
        opt[dau2] = min(abs(*it - dau2), abs(*(it - 1) - dau2));

    it = lower_bound(all(a), cuoi2);
    if (it == a.end())
        --it;
    if (it == a.begin())
        opt[cuoi2] = abs(*it - cuoi2);
    else
        opt[cuoi2] = min(abs(*it - cuoi2), abs(*(it - 1) - cuoi2));
    ll res1 = min(abs(dau1 - dau2) + abs(cuoi1 - cuoi2), abs(dau1 - cuoi2) + abs(cuoi1 - dau2));
    ll res2 = min({abs(dau1 - dau2) + opt[cuoi1] + opt[cuoi2], abs(dau1 - cuoi2) + opt[cuoi1] + opt[dau2], abs(cuoi1 - dau2) + opt[dau1] + opt[cuoi2], abs(cuoi1 - cuoi2) + opt[dau1] + opt[dau2]});
    ll res3 = opt[dau1] + opt[cuoi1] + opt[dau2] + opt[cuoi2];
    cout << min({res1, res2, res3}) << endl;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}